#pragma once
#include "heap.h"
template<typename RanIt, typename Pred>
class ISort
{
public:
	virtual void sort( RanIt first, RanIt last, Pred pred ) = 0;
};

template<typename RanIt, typename Pred>
class heapSort: 
	public ISort<RanIt, Pred>
{
public:
	void sort( RanIt first, RanIt last, Pred pred )
	{
		
	
	}

private: 

};

void swap(int* arr, int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j]= tmp;
}

int findpivot(int* arr, int i, int j)
{
	return i + (j-i)/2;
}

int partition( int* arr, int l, int r, int pivot)
{
	do{
		while( arr[++l] < pivot  );
		while( ( r !=0 ) && (arr[--r] > pivot));
		swap(arr, l ,r);
		
	}while( l < r);
	swap(arr, l, r);
	return l; //firt position in right partition
}

void qsort( int* arr, int i, int j)
{
	if( j <= i ) return;
	int pivotindex = findpivot(arr, i, j);
	swap(arr, pivotindex, j);
	int k = partition(arr,i-1, j, arr[j]);
	swap(arr, k, j);
	qsort(arr, i, k-1);
	qsort(arr, k+ 1, j);
}